package algorithmic_data_structure.归并排序;

import org.junit.Test;

public class offer51_reversePair {
    //在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
    // 输入一个数组，求出这个数组中的逆序对的总数。
    public int reversePairs(int[] nums) {
        return mergeSort(nums,0,nums.length-1);
    }

    public int mergeSort(int[] nums, int left, int right){
        if (left >= right){
            return 0;
        }
        int mid = left + (right-left)/2;
        int m1 = mergeSort(nums,left,mid);
        int m2 = mergeSort(nums,mid+1,right);
        int m3 = merge(nums,left,mid,right);
        return m1+m2+m3;
    }

    private int merge(int[] nums, int left, int mid, int right) {
        int res = 0;
        int[] help = new int[right - left + 1];
        int l = left,r = mid+1;
        int index = 0;
        while (l <= mid && r <= right){
            //这里“取等于”很关键，如果只是普通的归并排序取等号是为了为了稳定性
            //例如 ： 左部 2 5 6 7 ，右部 1 2 2 3,当下标分别为 l = 0 ，r = 1时，如果右移的是r，那么将会影响到下一个5，所以只能右移l
//            help[index++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
            //移动右部不用变化
            if (nums[l] <= nums[r]){
                help[index++] = nums[l++];
                res += r - (mid+1);
            }else{
                help[index++] = nums[r++];
            }
        }
        //如果左部还剩，那么这些剩余的元素 与 全部右部元素都能组成逆序对
        while (l <= mid){
            res += right-mid;
            help[index++] = nums[l++];
        }
        while (r <= right){
            help[index++] = nums[r++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            nums[i] = help[index++];
        }
        return res;
    }
    @Test
    public void test(){
        System.out.println(reversePairs(new int[]{7, 5, 6, 4}));
        System.out.println(reversePairs(new int[]{7,5,6,4,1,2,3,4}));//20
    }
}
